'''
https:#leetcode.cn/problems/lru-cache/description/
'''

class Node:
    def __init__(self, k = -1, v = -1, next = None, last = None):
        self.k = k
        self.v = v
        self.next = next
        self.last = last

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.dic = {}
        # 哨兵，头尾
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.last = self.head

    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        node = self.dic[key]
        self.move_to_head(node)
        return node.v


    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            node = self.dic[key]
            node.v = value
            self.move_to_head(node)
        else:
            node = Node(k = key, v = value)
            self.dic[key] = node
            if self.size < self.capacity:
                self.size += 1
            else:
                del_node = self.rm_last_node()
                del self.dic[del_node.k]
            self.add_to_head(node)

    def add_to_head(self, node):
        next = self.head.next
        node.last = self.head
        node.next = next
        self.head.next = node
        next.last = node


    def move_to_head(self, node):
        # 删除自己
        last, next = node.last, node.next
        last.next = next
        next.last = last

        # 插入前边
        next = self.head.next
        node.last = self.head
        node.next = next
        self.head.next = node
        next.last = node

    def rm_last_node(self):
        target = self.tail.last
        prev = target.last

        prev.next = self.tail
        self.tail.last = prev
        return target

lRUCache = LRUCache(2)
lRUCache.put(1, 1) # 缓存是 {1=1}
lRUCache.put(2, 2) # 缓存是 {1=1, 2=2}
print(lRUCache.get(1))
lRUCache.put(3, 3) # 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
print(lRUCache.get(2))
lRUCache.put(4, 4) # 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
print(lRUCache.get(1))
print(lRUCache.get(3))
print(lRUCache.get(4))